/********************************线性单链表抽象数据类型ADT定义**********************************************
   ADT LNode 
   {
        数据对象：D＝{ ai | ai ∈ElemSet, i=1,2,...,n,  n≥0 } 
        数据关系：R1＝{ <ai-1 ,ai >|ai-1 ,ai∈D,  i=2,...,n }
        基本操作：
                 （1）线性链表的初始化操作 
				      InitList（&L,n）
                      操作结果：将L初始化为空表,申请空间的大小为n。     
                 （2）线性链表的置空操作 
				      ClearList(&L) 
                      初始条件：线性表L已存在且不为空 。
                      操作结果：将表L置为空表。
                 （3）线性链表的判空操作 
				      ListIsEmpty(&L)
                      初始条件：线性表L已存在。
                      操作结果：如果L为空表则返回1，否则返回0。
                 （4）获取线性链表元素个数的操作 
				      ListLength（L）
                      初始条件：线性表L已存在。
                      操作结果：如果L为空表则返回0，否则返回表中的元素个数。
                 （5）获取线性链表第i个元素的操作（用元素的位序查找元素的值） 
				      GetItem(L,i,&e)
                      初始条件：表L已存在且不为空，1<=i<=ListLength(L)。
                      操作结果：用e返回L中第i个元素的值。
                 （6）线性链表插入元素操作 
				      ListInsert(&L,i,e)
                      初始条件：表L已存在且不为空，e为合法元素值且1≤i≤ListLength(L)+1。
                      操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。
                 （7）输出线链性表元素操作 
				      PrintList(&L) 
                      初始条件：线性表L已存在且不为空。
                      操作结果：线性表L中的所有元素已输出。 
                 （8）销毁线性链表操作 
				      DestroyList(&L) 
                      初始条件：线性表L已存在。
                      操作结果：将L销毁。                      
   }
****************************************************************************************************/
 
//*******************************************引入头文件*********************************************
#include <stdio.h>   //使用了标准库函数 
#include <stdlib.h>  //使用了动态内存分配函数 
#include <windows.h>

//******************************************自定义符号常量******************************************* 

#define OVERFLOW -2         //内存溢出错误常量
#define ILLEGAL -1          //非法操作错误常量 
#define OK 1                //表示操作正确的常量 
#define ERROR 0             //表示操作错误的常量

//******************************************自定义数据类型********************************************

typedef int Status;       //用typedef给int起个别名，也便于程序的维护 
typedef int ElemType;   //用typedef给float起个别名，也便于程序的维护
 
typedef struct LNode {    //用C语言描述线性单链表的结构，声明结构体的同时声明一个结构体指针 
	ElemType data;            //数据域 
	struct LNode *next;       //指针域 
}LNode, * LinkList; 

/*说明：该操作等价于： 
     struct LNode   //先声明一个结构体 
     {
	     ElemType data;            //数据域 
	     struct LNode *next;       //指针域 
     };
     typedef LNode * LinkList;     //声明一个结构体指针 
*/
 
//******************************************线性表的主要操作****************************************** 

//1.-------------------------------------线性单链表的初始化操作--------------------------------------- 

/*
	函数：MallocList_L
	参数：LinkList &L 带回创建的节点  
	返回值：状态码，OK表示操作成功 
	作用：申请一个节点的内存空间
*/
Status MallocList_L(LinkList &L) {	
	//为线性表L开辟内存空间，只申请一个结点的内存空间;malloc的返回值是一个指针，指向一段可用内存的起始地址
	L = (LNode*)malloc(sizeof(LNode));
	if(!L) {  //if(!L) <=> if(L == NULL) 
		printf("申请内存失败！\n");
		exit(OVERFLOW);  //退出程序，并提示用户内存分配失败的原因是内存泄露 
	}
	
	//操作成功 
    return OK; 
}

/*
	函数：InitList_L
	参数：LinkList &L 单链表的头指针。&L存放的是L指针变量的地址，L存放的是malloc后的头结点的地址
	      int n 线性表元素的个数 
	返回值：状态码，OK表示操作成功 
	作用：构造一个线性表并将其初始化 
*/
Status InitList_L(LinkList &L, int n){
	// printf("没有赋值前");
	// printf("LinkList &L的L = %p\n",L); 空
	// printf("LinkList &L的&L = %p\n",&L); La的地址
	// // printf("LinkList &L的*L = %p\n",*L);这个会报错,因为没有

	//工作指针 
	LinkList p;
	
	//先构造一个空的单链表，完成头结点的创建 
	MallocList_L(L);	
	//头结点数据域记录了单链表的长度，由于初始化了n个元素，所以赋值n 
	L->data = n;
	//将头结点的指针域设置为NULL 
	L->next = NULL;  
    
	//2.使用尾插法创建带头结点的单链线性表L，按照正常位序输入元素
	printf("请依次输入元素的值（用空格隔开）：\n");
	LinkList tail = L;
	for(int i = 0; i < n; i++){
		
		//生成一个新结点，使p指向此结点
		MallocList_L(p);
		
		//从键盘接收元素值，并存入p指向结点的数据域 
		scanf("%d", &(p->data));
		
		//将新申请的结点的指针域设为NULL，因为p结点要作为新的表尾结点使用，所以后面没有后继 
		p->next = NULL;
		
		//将p节点链接到当前表尾元素的后面，成为新的表尾结点 
		tail->next = p;
		
		//p成为了新的表尾结点，修改tail使其指向p
		tail = p;   
	}
	
	// printf("赋值后");	
	// printf("LinkList &L的L = %p\n",L); malloc生成的地址，也是La的值
	// printf("LinkList &L的&L = %p\n",&L); La的地址
	// printf("LinkList &L的*L = %p\n",*L);
	// printf("LinkList &L的L本质是 = %p\n",&(L->data)); n的值
	//操作成功 
	return OK;  
}
 
//2.-------------------------------------判断线性单链表是否为空------------------------------------

/*
	函数：ListIsEmpty_L
	参数：LinkList &L 单链表的头指针 
	返回值：如果线性表是空表返回1，否则返回0 
	作用：判断线性表L是否为空 
*/
int ListIsEmpty_L(LinkList &L) {
	
	//如果头结点后面有节点，那么单链表就不为空
	//L->next == NULL表示头结点后面没有节点 
    return L->next == NULL; 
}

//3.------------------------------------线性单表中插入元素的操作-----------------------------------

/*
	函数：ListInsert_L
	参数：LinkList &L 单链表的头指针 
	      int i 插入位置i 
	      ElemType e 插入元素e 
	返回值：状态码，OK表示操作成功，ERROR表示操作失败 
	作用：在带头结点的线性单链表L中第i个位置之前插入元素e
*/
Status ListInsert_L(LinkList &L, int i, ElemType e){
	
	//工作指针 
	LinkList p = L,s;
	
	//计数器，临时变量，用于记录查找插入位置的下标情况 
	int j = 0;
	
	//遍历单链表，寻找第i-1个结点，并使p指向该节点
	//while(p && j < i - 1) <=> while(p != NULL && j < i - 1)
	while(p && j < i - 1){
		p = p->next; //向后查找 
		++j;
	}
	
	//检查是否找到了第i-1个结点，如果p为空或者j超过了i-1
	//就说明没找到第i-1个结点，p为空表示当前线性表节点数小于i-1
	//j > i-1说明索引j越界了 
	if(!p || j > i - 1) { // if(!p || j > i - 1) <=> if(p == NULL || j > i - 1)
	    return ERROR;   
	}
	
	//如果执行到了这里，说明找到了第i-1个结点，此时p指向第i-1个结点 
	
	//生成一个新结点，并使s指向该节点 
	MallocList_L(s);
	
	//将待插入的元素e设置到新节点s的数据域 
	s->data = e;
	
	//将第i个结点及其后面的结点链接到结点s的后面（接管p的后继以及后面的结点） 
	s->next = p->next;
	
	//将s链接到p结点（也就是第i-1个结点）后面 
	p->next = s;
	
	//头结点数据域存储的单链表表长+1 
	L->data += 1; //L->data += 1;  <=>  L->data = L->data + 1;
	
	//操作成功 
	return OK; 
}
 
//4.------------------------------------线性单链表中删除元素的操作-----------------------------------

/*
	函数：ListDelete_L
	参数：LinkList &L 单链表的头指针 
	      int i 删除位置i 
	      ElemType &e 带回被删除元素e，这里没啥用，真的需要，可以return这个值，这样感觉不好
	返回值：状态码，OK表示操作成功，ERROR表示操作失败 
	作用：在带头结点的线性单链表L中,删除第i个元素,并由e返回其值
*/
Status ListDelete_L(LinkList &L, int i, ElemType &e){
	
	//工作指针q 
	LinkList q;
	
	//对空表做删除操作没有意义，要先判断单链表是否为空 
	// if(ListIsEmpty_L(L)) <=> if(ListIsEmpty_L(L) != 0)
	if(ListIsEmpty_L(L)) { 
	    return ERROR; 
	}
	
	//工作指针p，指向单链表头结点 
	LinkList p = L;
	
	//计数器，临时变量，用于记录查找删除位置的下标情况 
	int j = 0;
	
	//遍历单链表，寻找第i-1个结点，并使p指向该节点 
	// while(p->next && j < i - 1) <=> while(p->next != NULL && j < i - 1)
	while(p->next && j < i - 1) {
		p = p->next; //向后查找 
		++j;
	} 
	
	//检查是否找到了第i-1个结点，如果p的后继指针域为空或者j超过了i-1
	//就说明没找到第i-1个结点，p的后继指针域为空表示当前线性表节点数小于i-1
	//j > i-1说明索引j越界了
	// if(!(p->next) || j > i - 1) <=> if(p->next == NULL || j > i - 1)
	if(!(p->next) || j > i - 1) {
		return ERROR; 
	}
	
	//如果执行到了这里，说明找到了第i-1个结点，此时p指向第i-1个结点
	
	//使q指向第i个结点，此节点就是要删除的结点 
	q = p->next;
	
	//将q（第i+1个结点）后面的结点链接到p（第i-1个结点）的后面，
	//将q指向的结点隔离出单链表，即删除第i各节点 
	p->next = q->next; 
	
	//保存q结点数据域存储的值到e 
	e = q->data;
	
	//释放q指向节点（第i个结点）的空间 
	free(q);
	
	//删除元素后头结点保存的表长-1 
	L->data -= 1; //L->data -= 1;  <=>  L->data = L->data - 1;
	
	//操作成功 
	return OK; 
}

//5.------------------------------------线性单链表中查找元素的操作-----------------------------------

/*
	函数：compare
	参数：ElemType x 待比较的第一个元素 
	      ElemType y 待比较的第二个元素 
	返回值：如果元素x和y的值相等，返回1，否则返回0 
	作用：比较两个元素是否相等 
*/
Status compare(ElemType x, ElemType y){  //比较函数
 
	return x == y;
}

/*
	函数：LocateElem_L
	参数：LinkList L 单链表的头指针 
	      ElemType e 查找值为e的元素 
		  Status (*compare)(ElemType,ElemType) 函数指针，指向比较元素是否相同的函数 
	返回值：查找到元素在单链表L中的位置，若没有找到，返回0 
	作用：在单链表L中查找第一个值e满足compare()的元素在单链表中的位置 
*/
Status LocateElem_L(LinkList L, ElemType e, Status (*compare)(ElemType, ElemType)){
	
	//对空表执行查找操作没有意义，判断单链表是否为空 
	if(ListIsEmpty_L(L)) { // if(ListIsEmpty_L(L)) <=> if(ListIsEmpty_L(L) != 0)
	    return ERROR;
	}
	
	//工作指针p 
	LinkList p;
	
	//临时变量i，记录了查找到的元素的位置 
	int i = 0; 
	
	//从首元结点（头结点后面的第一个结点）开始查找 
	p = L->next;
	
	//调用compare函数遍历线性表，找到值为e的元素
	// while(p && !(*compare)(p->data, e)) <=> while(p != NULL && (*compare)(p->data, e) == 0) 
	while(p && !(*compare)(p->data, e)){
		++i;
		p = p->next; //向后查找 
	}
	
	//如果找到了值为e的元素，就返回元素所在位置
	// if(p && i <= (int)(L->data))  <=>  if(p != NULL && i <= (int)(L->data))
	if(p && i <= (int)(L->data)) {
		
		//因为i是从0开始自增的，元素位置是从1开始计算的，所以这里要+1才是元素的位置
		return i + 1;
    }	
	else {
		return 0; 
	}
} 

//6. -----------------------------------线性单链表中合并元素的操作---------------------------------

/*
	函数：MergeList_L
	参数：LinkList &La 被合并单链表a的头指针
	      LinkList &Lb 被合并单链表b的头指针
		  LinkList &Lc 单链表a和b合并后得到单链表c 
	返回值：状态码，操作成功返回OK，操作失败返回ERROR 
	作用：已知线性单链表La和Lb的元素按值非递减排列，
	      归并La和Lb得到新的线性单链表Lc，Lc的元素也按值非递减排列 
*/
Status MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc){
	
	//对空表进行合并操作没有意义，合并前需要先判断单链表是否为空 
	// if(ListIsEmpty_L(La)) <=> if(ListIsEmpty_L(La) != 0)
	if(ListIsEmpty_L(La)) { 
	    return ERROR;
	}
	
	// if(ListIsEmpty_L(Lb)) <=> if(ListIsEmpty_L(Lb) != 0)
	if(ListIsEmpty_L(Lb)) {
	    return ERROR;
	}
	
	// if(ListIsEmpty_L(Lc)) <=> if(ListIsEmpty_L(Lc) != 0)
	if(ListIsEmpty_L(Lc)) {
	    return ERROR;
	}
	
	//工作指针pa、pb、pc，分别用于指向a、b、c三个单链表的节点 
	LinkList pa, pb, pc;
	
	//设置工作指针的初始位置 
	pa = La->next;  //使pa指向单链表a的首元结点（头结点后面的第一个数据节点） 
	pb = Lb->next;  //使pb指向单链表b的首元结点（头结点后面的第一个数据节点）
	Lc = pc = La;   //用线性表a的头结点作为线性表c的头结点
	
	//循环继续的条件：单链表La和Lb的工作指针不同时为空（两个表都没有完成遍历操作）
	// while(pa && pb) <=> while(pa != NULL && pb != NULL)
	while(pa && pb) {
		
		/*基本思想：判断pa和pb所指结点的元素哪个小，if(pa->data <= pb->data)
		 
		           *若pa所指结点的元素较小，        pa->data <= pb->data
					  就将pa所指结点链入Lc中，      pc->next = pa;
					  然后使pc和pa都指向pa所指结点，pc = pa;
					  最后pa在原来的链上后移一位    pa = pa->next;
					  
				   *若pb所指结点的元素较小，        pb->data <= pa->data
					  就将pb所指结点链入Lc中，      pc->next = pb;
					  然后使pc和pb都指向pb所指结点，pc = pb;
					  最后pb在原来的链上后移一位    pb = pb->next;
		*/  
		
		//pa所指结点元素大于pb所指结点元素
		if(pa->data <= pb->data) { 
		
			pc->next = pa;  //将pa所指结点链入Lc中 
			pc = pa;        //使pc、pa指向同一结点 
			pa = pa->next;  //pa移向原来La链上当前位置的下一个结点 
		}
		else {   //pa所指结点元素小于pb所指结点元素 
		
			pc->next = pb;  //将pb所指结点链入Lc中 
			pc = pb;        //使pc、pb指向同一结点
			pb = pb->next;  //pb移向原来Lb链上当前位置的下一个结点 
		}
	}
	
	//条件表达式：  条件？表达式1:表达式2    若条件为真，执行表达式1，否则执行表达式2 
	//pc->next = pa说明单链表a还有结点没处理完，同理pc->next = pb表示单链表b还有结点没处理完 
	pc->next = pa ? pa : pb;   //插入剩余段
	
	//操作成功 
	return OK;	 
}

//7.--------------------------------------线性单链表的销毁操作-------------------------------------

/*
	函数：DestoryList_L
	参数：LinkList &L 被销毁单链表的头指针
	返回值：状态码，操作成功返回OK，操作失败返回ERROR 
	作用：销毁单链表L，释放所有结点（包括头结点）的内存空间 
*/
Status DestoryList_L(LinkList &L){
	
	//工作指针q，指向被删除结点L的后继 
	LinkList q;
	
	//循环处理单链表中的每一个结点 
	while(L){ // while(L) <=> while(L != NULL)
	
		//使q指向被删除节点的后继
		q = L->next;
		
		//释放L指向的被删除结点的内存空间
		free(L);
		
		//使q成为下一个待删除节点
		L = q;
	}
	 
	printf("线性单链表内存释放成功！\n");
	
	//操作成功 
	return OK; 
}

//8.--------------------------------------线性单链表的排序操作------------------------------------

/*
	函数：SortList_L
	参数：LinkList &L 被排序单链表的头指针 
	返回值：状态码，操作成功返回OK，操作失败返回ERROR 
	作用：将单链表L中的元素排序,使用冒泡法，排序完成后元素按升序排列  
*/
Status SortList_L(LinkList &L) {
   
	/* 冒泡法
	   ->基本思路：（以升序为例）含有n个元素的数组原则上要进行n-1次排序。
	                对于每一躺的排序，从第一个数开始，依次比较前一个数与后一个数的大小。
					如果前一个数比后一个数大，则进行交换。
					这样一轮过后，最大的数沉到最后的位置。
					第二轮则去掉最后一个数，对前n-1个数再按照上面的步骤找出最大数，
					该数将称为倒数第二的数组元素......n-1轮过后，就完成了排序。
	   ->若果有n个数，则要进行n-1趟比较 
	*/
	
	//对空表做排序操作没有意义，所以要先判断单链表是否为空表 
	if(ListIsEmpty_L(L)) { 
	    return ERROR;
	}
	
	//i代表冒泡的趟数，j代表元素的位序
    int i, j;
	
	//e1和e2是两个临时变量 n存储了单链表的长度 
	ElemType e1, e2, n = L->data;
	
	//工作指针p 
	LinkList p;
	
	//外循环控制循环趟数
	for(i = 0; i < n - 1; i++) {
    	
    	//使p指向首元结点 
    	p = L->next;
    	
    	//内循环选择要进行比较的数
        for(j = 0; j < n - 1 - i; j++) { 
            
			//取第i个元素	
	        e1 = p->data;
			
			//取第i+1个元素      
	        e2 = p->next->data; 
			
			//若想改为降序排列，将这里的>改为<即可   
            if (e1 > e2) {
            	
			    //交换e1和e2的值
                p->data = e2;        
				p->next->data = e1;  
            }
            
            //使工作指针p向后移动，指向下一个节点 
            p = p->next;
        }
    }
	return OK;
}

//9.--------------------------------------线性单链表的输出操作------------------------------------

/*
	函数：Print
	参数：ElemType e 被访问的元素 
	返回值：状态码，操作成功返回OK，操作失败返回ERROR 
	作用：访问元素e的函数，通过修改该函数可以修改元素访问方式，
	      该函数使用时需要配合遍历函数一起使用。 
*/
Status Print(ElemType e) {
	
	//指定元素的访问规则：按指定格式打印输出 
	// printf("%6.2f ", e); // 之前是float的data，改成了int类型
	printf("%d",e);
	
	//操作成功 
	return OK;
}

/*
	函数：ListTraverse_L
	参数：LinkList L 单链表L的头指针 
	      Status(* visit)(ElemType) 函数指针，指向元素访问函数。 
	返回值：状态码，操作成功返回OK，操作失败返回ERROR 
	作用：调用元素访问函数完成单链表L的遍历，所谓遍历就是逐一访问线性表中的每个元素。 
*/
Status ListTraverse_L(LinkList L, Status(* visit)(ElemType)) {
	
	//工作指针p 
	LNode *p;
	
	//使p指向单链表L的首元结点 
	p = L->next;
	
	//对单链表L的每个数据节点依次进行访问 
	while(p){ // while(p) <=> while(p != NULL)
	
		//调用Visit函数对元素进行访问
		// if(!visit(p->data)) <=> if(visit(p->data) == 0) 
		// 等价于直接使用Printf(p->data)
		if(!visit(p->data)) { 
			
			//如果遍历过程中某个元素访问失败，则遍历没有进行下去的意义
			return ERROR;
		}
		
		//使工作指针p指向单链表下一个结点 
		p = p->next;
	}
	
	//操作成功 
	return OK;	
}

//10.--------------------------------置线性单链表任意一个元素的操作-------------------------------

/*
	函数：putElem_L
	参数：LinkList &L 被修改的单链表L的头指针 
	      int i 被修改元素所在位置
		  ElemType e 修改第i个位置的元素值为e 
	返回值：状态码，操作成功返回OK，操作失败返回ERROR 
	作用：当第i个元素存在时，将其值置为e，并返回OK，否则返回ERROR 
*/
Status putElem_L(LinkList &L, int i, ElemType e) {
	
	//对空表进行修改操作没有意义，所以要先检查单链表是否为空表 
	if(ListIsEmpty_L(L)) {  // if(ListIsEmpty_L(L)) <=> if(ListIsEmpty_L(L) != 0) 
	    return ERROR;
	}
	
	//工作指针p 
	LinkList p;
	
	//使工作指针p指向首元结点 
	p = L->next;
	
	//j为计数器，记录了遍历的元素的个数
	int j = 1;
	
	//先判断i是否合法，若不合法直接退出，防止i越界 
	if(i < 0){ 
	
	    printf("您输入的元素位序不合法，请输入一个非负的整数！");
	    return ERROR;  //第i个元素不存在 
	}
	
	//遍历单链表查找第i个元素 
	while(p && j < i) { // while(p && j < i) <=> while(p != NULL && j < i)
		p = p->next;    
		++j; 
	}
	
	//没找到第i个元素 
	if(!p || j > i) { // if(!p || j > i) <=> if(p == NULL || j > i) 
	    return ERROR;
	}
	
	//置第i个元素的值为e 
	p->data = e;
	
	//操作成功 
	return OK; 
}

//10.--------------------------------得到线性单链表固定位置元素的操作-----------------------------

/*
	函数：GetElem_L
	参数：LinkList L 单链表L的头指针 
	      int i 元素所在位置
		  ElemType &e 带回第i个位置的元素值 
	返回值：状态码，操作成功返回OK，操作失败返回ERROR 
	作用：当第i个元素存在时，将其值赋给e，并返回OK，否则返回ERROR 
*/
Status GetElem_L(LinkList L, int i, ElemType &e) {
	
	//对空表进行查找操作没有意义，所以要先判断单链表是否为空 
	if(ListIsEmpty_L(L)) { // if(ListIsEmpty_L(L)) <=> if(ListIsEmpty_L(L) != 0)
	    return ERROR;
	}
	
	//工作指针p 
	LinkList p;
	
	//使p指向首元结点 
	p = L->next;
	
	//j为计数器，记录了遍历元素的个数
	int j = 1;
	
	//判断i的值是否合法，防止i越界 
	if(i < 0) { 
	    return ERROR;
	}
	
	//遍历单链表查找第i个元素 
	while(p && j < i) {   // while(p && j < i) <=> while(p != NULL && j < i) 
	
		p = p->next;
		++j; 
	}
	
	//没找到第i个元素 
	if(!p || j > i) {
		return ERROR;
	} 
	
	//取第i个元素的值 
	e = p->data;
	
	//操作成功        
	return OK; 
}


//**********************************************主函数******************************************** 
int main(int argc, char *argv[]){ 	
    system("chcp 65001 > nul");

	//定义头结点的指针变量(不知道是不是头指针)，里面存放的应该是头节点的内存位置
	LinkList La, Lb, Lc;
    ElemType e;
    int n = 0, i;
	 
	printf("---------------------------------测试初始化功能---------------------------------\n");
	
	printf("->初始化单链表La\n");
	printf("您想给单链表La设置多少个元素：");           //初始化La 
	scanf("%d", &n);	 
	InitList_L(La, n);
	
	printf("->初始化单链表Lb\n");
	printf("您想给单链表Lb设置多少个元素：");           //初始化Lb 
	scanf("%d", &n);	 
	InitList_L(Lb, n);
	
	printf("初始化La,Lb成功！\n\n");
	
	
	printf("----------------------------------测试输出功能----------------------------------\n"); 

    printf("->输出单链表La\n");      //输出原始结果，以供后面参考 
	ListTraverse_L(La, Print); 
	
	printf("\n->输出单链表Lb\n");
	ListTraverse_L(Lb, Print);
	
	printf("\n输出操作成功！\n\n");
	
	
	printf("\n----------------------------------测试插入功能----------------------------------\n"); 
	
	printf("->测试单链表La插入\n");    //为线性表La插入一个元素                    
	printf("您想在单链表La的哪个位置之前插入值？\n");
	scanf("%d", &i);
	printf("您想在单链表La的该位置之前插入的值为多少？\n");
	scanf("%f", &e);
	ListInsert_L(La, i, e);
	printf("执行插入操作后单链表La的所有元素为：\n");      //输出执行操作后的单链表，以便与原始结果对比 
	ListTraverse_L(La, Print);
	
	printf("\n->测试单链表Lb插入\n");    //为线性表Lb插入一个元素                    
	printf("您想在单链表Lb的哪个位置之前插入值？\n");
	scanf("%d", &i);
	printf("您想在单链表Lb的该位置之前插入的值为多少？\n");
	scanf("%f", &e);
	ListInsert_L(Lb, i, e);
	printf("执行插入操作后单链表Lb的所有元素为：\n");      //输出执行操作后的单链表，以便与原始结果对比 
	ListTraverse_L(Lb, Print);
	
	printf("插入操作成功！\n\n");
	

	printf("----------------------------------测试删除功能----------------------------------\n");
	
	printf("->现在在La中删除元素\n");                        //在La中删除一个元素 
	printf("您想在单链表La的哪个位置之前删除值？\n");
	scanf("%d", &i);
	ListDelete_L(La, i, e);
	printf("被删除的元素为%f\n", e);
	printf("执行删除操作后单链表L1的所有元素为：\n");      //输出执行操作后的单链表，以便与原始结果对比 
	ListTraverse_L(La, Print);
	
    printf("\n->现在在Lb中删除元素\n");                        //在Lb中删除一个元素 
	printf("您想在单链表Lb的哪个位置之前删除值？\n");
	scanf("%d", &i);
	ListDelete_L(Lb, i, e);
	printf("被删除的元素为%f\n", e);
	printf("执行删除操作后单链表L2的所有元素为：\n");      //输出执行操作后的单链表，以便与原始结果对比 
	ListTraverse_L(Lb, Print);
	printf("\n删除操作执行完毕！\n\n");
	

	printf("---------------------------------测试取元素功能---------------------------------\n");
	
	printf("->现在在La中取元素\n");                        //在La中取一个元素 
	printf("您想取单链表La中的第几个元素？\n");
	scanf("%d", &i);
	GetElem_L(La, i, e);
	printf("取得的元素为%f\n", e);
	
    printf("->现在在Lb中取元素\n");                        //在Lb中取一个元素 
	printf("您想取单链表Lb中的第几个元素？\n");
	scanf("%d", &i);
	GetElem_L(Lb, i, e);
	printf("取得的元素为%f\n", e);
	
	printf("\n取值操作执行完毕！\n\n");
	

	printf("---------------------------------测试置元素功能---------------------------------\n");
	
	printf("->现在在La中置元素\n");                        //在La中置一个元素 
	printf("您想置换单链表La中的第几个元素？\n");
	scanf("%d", &i);
	printf("您想置换单链表La中的第%d个元素为多少？\n",i);
	scanf("%f", &e);
	putElem_L(La, i, e);
	printf("执行重置操作后单链表La的所有元素为：\n");      //输出执行操作后的单链表，以便与原始结果对比 
	ListTraverse_L(La, Print);
	
    printf("\n->现在在Lb中置元素\n");                        //在La中置一个元素 
	printf("您想置单链表Lb中的第几个元素？\n");
	scanf("%d", &i);
	printf("您想置换单链表Lb中的第%d个元素为多少？\n",i);
	scanf("%f", &e);
	putElem_L(Lb, i, e);
	printf("执行重置操作后单链表Lb的所有元素为：\n");      //输出执行操作后的单链表，以便与原始结果对比 
	ListTraverse_L(Lb, Print);
	
	printf("\n重置操作执行完毕！\n\n");


	printf("----------------------------------测试查找功能----------------------------------\n");
	
	printf("您想在单链表La中查找的值为：\n");
	scanf("%f", &e);
	i = LocateElem_L(La, e, compare);
	if(i == 0) { 
		printf("对不起，没有找到您输入的元素！\n");
    } 
	else {
		printf("恭喜，找到啦！您想要的元素在表中的位序为%d\n", i);
	}   
	   
    printf("您想在线性表Lb中查找的值为：\n");
	scanf("%f", &e);
	i = LocateElem_L(Lb, e, compare);
	if(i == 0) {
		printf("对不起，没有找到您输入的元素！\n");
	}	
    else {
    	printf("恭喜，找到啦！您想要的元素在表中的位序为%d\n", i);
    }//else
		 
	printf("\n查找操作执行完毕！\n\n");	
	
	//----------------------------------测试排序功能--------------------------------------------
	printf("----------------------------------测试排序功能----------------------------------\n"); 
	
	printf("排序前 La、Lb的元素为：\n");
	printf("->单链表La的所有元素：\n");
	ListTraverse_L(La, Print);                          //在执行操作之前先输出一遍所有元素，以供参考 
	printf("\n->单链表Lb的所有元素：\n");
	ListTraverse_L(Lb, Print);
	
	SortList_L(La);                            //分别对La和Lb进行排序 
	SortList_L(Lb); 
	
	printf("\n排序后 La、Lb的元素为：\n");
	printf("->单链表La的所有元素：\n");
	ListTraverse_L(La, Print);                          //执行操作之后再输出一遍所有元素
	printf("\n->单链表Lb的所有元素：\n");
	ListTraverse_L(Lb, Print);
	
	printf("\n排序操作执行完毕！\n\n");
	
	//-------------------------------测试归并(合并)功能-----------------------------------------
	printf("----------------------------------测试归并功能----------------------------------\n");
		
    printf("->初始化线性表Lc\n");
	MallocList_L(Lc);         //为线性表Lc申请头结点的内存空间，但不初始化，用于保存合并后的结果
	Lc->data = 0;   //设置元素个数为0 
	printf("线性表Lc初始化成功！开始归并操作\n\n");
	MergeList_L(La, Lb, Lc); 
	printf("->线性表L3的所有元素：\n");
	ListTraverse_L(Lc, Print); 
	
	printf("\n归并操作执行完毕！\n\n");
  	
	//----------------------------------测试销毁功能--------------------------------------------
	printf("----------------------------------测试销毁功能----------------------------------\n");

    //合并操作是就地执行的，操作过程中没有产生Lc,Lb也在操作过程中被销毁，所以这时只有一个待销毁的线性表 
    printf("->销毁线性表La：");
	DestoryList_L(La); 
	printf("销毁操作执行完毕！\n\n");
	
	printf("所有操作执行完毕，测试成功！\n"); 
	return 0;	
}

/* --------------------------------------运行结果------------------------------------------ 

	*******************************线性单链表测试程序*******************************
	
	---------------------------------测试初始化功能---------------------------------
	
	->初始化单链表La
	您想给单链表La设置多少个元素：5
	请依次输入元素的值（用空格隔开）：
	1 45 7 25 4
	->初始化单链表Lb
	您想给单链表Lb设置多少个元素：10
	请依次输入元素的值（用空格隔开）：
	1 45 25 87 45 56 23 41 23 56
	初始化La,Lb成功！
	
	----------------------------------测试输出功能----------------------------------
	
	->输出单链表La
	  1.00  45.00   7.00  25.00   4.00
	->输出单链表Lb
	  1.00  45.00  25.00  87.00  45.00  56.00  23.00  41.00  23.00  56.00
	输出操作成功！
	
	
	----------------------------------测试插入功能----------------------------------
	
	->测试单链表La插入
	您想在单链表La的哪个位置之前插入值？
	1
	您想在单链表La的该位置之前插入的值为多少？
	23
	执行插入操作后单链表La的所有元素为：
	 23.00   1.00  45.00   7.00  25.00   4.00
	->测试单链表Lb插入
	您想在单链表Lb的哪个位置之前插入值？
	6
	您想在单链表Lb的该位置之前插入的值为多少？
	56
	执行插入操作后单链表Lb的所有元素为：
	  1.00  45.00  25.00  87.00  45.00  56.00  56.00  23.00  41.00  23.00  56.00 插
	入操作成功！
	
	----------------------------------测试删除功能----------------------------------
	
	->现在在La中删除元素
	您想在单链表La的哪个位置之前删除值？
	6
	被删除的元素为4.000000
	执行删除操作后单链表L1的所有元素为：
	 23.00   1.00  45.00   7.00  25.00
	->现在在Lb中删除元素
	您想在单链表Lb的哪个位置之前删除值？
	2
	被删除的元素为45.000000
	执行删除操作后单链表L2的所有元素为：
	  1.00  25.00  87.00  45.00  56.00  56.00  23.00  41.00  23.00  56.00
	删除操作执行完毕！
	
	---------------------------------测试取元素功能---------------------------------
	
	->现在在La中取元素
	您想取单链表La中的第几个元素？
	3
	取得的元素为45.000000
	->现在在Lb中取元素
	您想取单链表Lb中的第几个元素？
	3
	取得的元素为87.000000
	
	取值操作执行完毕！
	
	---------------------------------测试置元素功能---------------------------------
	
	->现在在La中置元素
	您想置单链表La中的第几个元素？
	5
	您想置单链表La中的第5个元素为多少？
	23
	执行重置操作后单链表La的所有元素为：
	 23.00   1.00  45.00   7.00  23.00
	->现在在Lb中置元素
	您想置单链表Lb中的第几个元素？
	3
	您想置单链表Lb中的第3个元素为多少？
	89
	执行重置操作后单链表Lb的所有元素为：
	  1.00  25.00  89.00  45.00  56.00  56.00  23.00  41.00  23.00  56.00
	重置操作执行完毕！
	
	----------------------------------测试查找功能----------------------------------
	
	您想在单链表La中查找的值为：
	5
	对不起，没有找到您输入的元素！
	您想在线性表Lb中查找的值为：
	89
	恭喜，找到啦！您想要的元素在表中的位序为3
	
	查找操作执行完毕！
	
	----------------------------------测试排序功能----------------------------------
	
	排序前 La、Lb的元素为：
	->单链表La的所有元素：
	 23.00   1.00  45.00   7.00  23.00
	->单链表Lb的所有元素：
	  1.00  25.00  89.00  45.00  56.00  56.00  23.00  41.00  23.00  56.00
	排序后 La、Lb的元素为：
	->单链表La的所有元素：
	  1.00   7.00  23.00  23.00  45.00
	->单链表Lb的所有元素：
	  1.00  23.00  23.00  25.00  41.00  45.00  56.00  56.00  56.00  89.00
	排序操作执行完毕！
	
	----------------------------------测试归并功能----------------------------------
	
	->初始化线性表Lc
	线性表Lc初始化成功！开始归并操作
	
	->线性表L3的所有元素：
	  1.00   1.00   7.00  23.00  23.00  23.00  23.00  25.00  41.00  45.00  45.00  56
	.00  56.00  56.00  89.00
	归并操作执行完毕！
	
	----------------------------------测试销毁功能----------------------------------
	
	->销毁线性表La：线性单链表内存释放成功！
	销毁操作执行完毕！
	
	所有操作执行完毕，测试成功！
	
	--------------------------------
	Process exited with return value 0
	Press any key to continue . . .
*/ 